package com.haidechizi.sort;

import java.util.Arrays;

/**
 * @author: wangdejun
 * @create: 2020-03-14 10:30
 **/
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = new int[]{8, 3, 5, 0, 1, 4, 6, 7};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));

    }

    /**
     * 希尔排序
     * 1.确定步长，每次变为原来的一半，知道为0（初始值为length/2）
     * 从d开始，比较数组中的每个数
     * 将每轮中的数进行插入排序
     */
    public static void shellSort(int[] arr) {
        // 定义循环的次数（每次步长）
        for (int d = arr.length / 2; d > 0; d /= 2) {
            for (int i = d; i < arr.length; i++) {
                // 去除当前需要比较的基数
                int temp = arr[i];
                int j;
                for (j = i - d; j >= 0 && arr[j] > temp; j -= d) {
                    arr[j + d] = arr[j];
                }
                arr[j + d] = temp;
            }
        }
    }

}
